# coding=utf-8
# Date: 2021/8/29 09:54
from typing import List


# 执行用时：48 ms, 在所有 Python3 提交中击败了74.58%的用户
# 内存消耗：15 MB, 在所有 Python3 提交中击败了14.58%的用户
class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        s = [0] * (n + 1)
        for i in range(1, n + 1):
            s[i] = s[i - 1] + arr[i - 1]

        res = 0
        for l in range(1, n + 1, 2):
            for i in range(1, n - l + 2):
                j = i + l - 1
                res += s[j] - s[i - 1]
        return res


if __name__ == "__main__":
    print(Solution().sumOddLengthSubarrays([1, 4, 2, 5, 3]))
